home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / python2.4 / site-packages / Crypto / PublicKey / qNEW.py < prev    next >
Text File  |  2006-06-22  |  6KB  |  171 lines
  1. #
  2. #   qNEW.py : The q-NEW signature algorithm.
  3. #
  4. #  Part of the Python Cryptography Toolkit
  5. #
  6. # Distribute and use freely; there are no restrictions on further
  7. # dissemination and usage except those imposed by the laws of your
  8. # country of residence.    This software is provided "as is" without
  9. # warranty of fitness for use or suitability for any purpose, express
  10. # or implied. Use at your own risk or not at all.
  11. #
  12.  
  13. __revision__ = "$Id: qNEW.py,v 1.8 2003/04/04 15:13:35 akuchling Exp $"
  14.  
  15. from Crypto.PublicKey import pubkey
  16. from Crypto.Util.number import *
  17. from Crypto.Hash import SHA
  18.  
  19. class error (Exception):
  20.     pass
  21.  
  22. HASHBITS = 160   # Size of SHA digests
  23.  
  24. def generate(bits, randfunc, progress_func=None):
  25.     """generate(bits:int, randfunc:callable, progress_func:callable)
  26.  
  27.     Generate a qNEW key of length 'bits', using 'randfunc' to get
  28.     random data and 'progress_func', if present, to display
  29.     the progress of the key generation.
  30.     """
  31.     obj=qNEWobj()
  32.  
  33.     # Generate prime numbers p and q.  q is a 160-bit prime
  34.     # number.  p is another prime number (the modulus) whose bit
  35.     # size is chosen by the caller, and is generated so that p-1
  36.     # is a multiple of q.
  37.     #
  38.     # Note that only a single seed is used to
  39.     # generate p and q; if someone generates a key for you, you can
  40.     # use the seed to duplicate the key generation.  This can
  41.     # protect you from someone generating values of p,q that have
  42.     # some special form that's easy to break.
  43.     if progress_func:
  44.         progress_func('p,q\n')
  45.     while (1):
  46.         obj.q = getPrime(160, randfunc)
  47.         #           assert pow(2, 159L)<obj.q<pow(2, 160L)
  48.         obj.seed = S = long_to_bytes(obj.q)
  49.         C, N, V = 0, 2, {}
  50.         # Compute b and n such that bits-1 = b + n*HASHBITS
  51.         n= (bits-1) / HASHBITS
  52.         b= (bits-1) % HASHBITS ; powb=2L << b
  53.         powL1=pow(long(2), bits-1)
  54.         while C<4096:
  55.             # The V array will contain (bits-1) bits of random
  56.             # data, that are assembled to produce a candidate
  57.             # value for p.
  58.             for k in range(0, n+1):
  59.                 V[k]=bytes_to_long(SHA.new(S+str(N)+str(k)).digest())
  60.             p = V[n] % powb
  61.             for k in range(n-1, -1, -1):
  62.                 p= (p << long(HASHBITS) )+V[k]
  63.             p = p+powL1         # Ensure the high bit is set
  64.  
  65.             # Ensure that p-1 is a multiple of q
  66.             p = p - (p % (2*obj.q)-1)
  67.  
  68.             # If p is still the right size, and it's prime, we're done!
  69.             if powL1<=p and isPrime(p):
  70.                 break
  71.  
  72.             # Otherwise, increment the counter and try again
  73.             C, N = C+1, N+n+1
  74.         if C<4096:
  75.             break   # Ended early, so exit the while loop
  76.         if progress_func:
  77.             progress_func('4096 values of p tried\n')
  78.  
  79.     obj.p = p
  80.     power=(p-1)/obj.q
  81.  
  82.     # Next parameter: g = h**((p-1)/q) mod p, such that h is any
  83.     # number <p-1, and g>1.  g is kept; h can be discarded.
  84.     if progress_func:
  85.         progress_func('h,g\n')
  86.     while (1):
  87.         h=bytes_to_long(randfunc(bits)) % (p-1)
  88.         g=pow(h, power, p)
  89.         if 1<h<p-1 and g>1:
  90.             break
  91.     obj.g=g
  92.  
  93.     # x is the private key information, and is
  94.     # just a random number between 0 and q.
  95.     # y=g**x mod p, and is part of the public information.
  96.     if progress_func:
  97.         progress_func('x,y\n')
  98.     while (1):
  99.         x=bytes_to_long(randfunc(20))
  100.         if 0 < x < obj.q:
  101.             break
  102.     obj.x, obj.y=x, pow(g, x, p)
  103.  
  104.     return obj
  105.  
  106. # Construct a qNEW object
  107. def construct(tuple):
  108.     """construct(tuple:(long,long,long,long)|(long,long,long,long,long)
  109.     Construct a qNEW object from a 4- or 5-tuple of numbers.
  110.     """
  111.     obj=qNEWobj()
  112.     if len(tuple) not in [4,5]:
  113.         raise error, 'argument for construct() wrong length'
  114.     for i in range(len(tuple)):
  115.         field = obj.keydata[i]
  116.         setattr(obj, field, tuple[i])
  117.     return obj
  118.  
  119. class qNEWobj(pubkey.pubkey):
  120.     keydata=['p', 'q', 'g', 'y', 'x']
  121.  
  122.     def _sign(self, M, K=''):
  123.         if (self.q<=K):
  124.             raise error, 'K is greater than q'
  125.         if M<0:
  126.             raise error, 'Illegal value of M (<0)'
  127.         if M>=pow(2,161L):
  128.             raise error, 'Illegal value of M (too large)'
  129.         r=pow(self.g, K, self.p) % self.q
  130.         s=(K- (r*M*self.x % self.q)) % self.q
  131.         return (r,s)
  132.     def _verify(self, M, sig):
  133.         r, s = sig
  134.         if r<=0 or r>=self.q or s<=0 or s>=self.q:
  135.             return 0
  136.         if M<0:
  137.             raise error, 'Illegal value of M (<0)'
  138.         if M<=0 or M>=pow(2,161L):
  139.             return 0
  140.         v1 = pow(self.g, s, self.p)
  141.         v2 = pow(self.y, M*r, self.p)
  142.         v = ((v1*v2) % self.p)
  143.         v = v % self.q
  144.         if v==r:
  145.             return 1
  146.         return 0
  147.  
  148.     def size(self):
  149.         "Return the maximum number of bits that can be handled by this key."
  150.         return 160
  151.  
  152.     def has_private(self):
  153.         """Return a Boolean denoting whether the object contains
  154.         private components."""
  155.         return hasattr(self, 'x')
  156.  
  157.     def can_sign(self):
  158.         """Return a Boolean value recording whether this algorithm can generate signatures."""
  159.         return 1
  160.  
  161.     def can_encrypt(self):
  162.         """Return a Boolean value recording whether this algorithm can encrypt data."""
  163.         return 0
  164.  
  165.     def publickey(self):
  166.         """Return a new key object containing only the public information."""
  167.         return construct((self.p, self.q, self.g, self.y))
  168.  
  169. object = qNEWobj
  170.  
  171.